package com.suxin.algorithm;

/**
 * @author Tang
 * @classname FibonacciSequence
 * @description [ 斐波那契数列 ]
 * @date 2022/4/21 14:09
 */
public class FibonacciSequence {

    /**
     * 尾递归实现
     * @param n
     * @return
     */
    public Integer fibonacci3(int n,int sum) {
        if (n <= 1) {
            return 1;
        }
        return fibonacci3(n-1,sum);
    }

    /**
     * 利用数组实现
     * @param n
     * @return
     */
    public Integer fibonacci2(int n) {
        int[] ints = new int[n];
        ints[0] = 1;
        ints[1] = 1;
        for (int i = 2; i < n; i++) {
            ints[i] = ints[i - 1] + ints[i - 2];
        }
        return ints[n - 1];
    }

    /**
     * 时间复杂度: n^2，，复杂度比较高
     * 原因：计算f(n),f(n-1)的值的时候,f(0 ~ n-1)都是重复的计算
     * @param n
     * @return
     */
    public Integer fibonacci1(int n) {
        if (n <= 1) {
            return 1;
        }
        return fibonacci1(n - 1) + fibonacci1(n - 2);
    }

    public static void main(String[] args) {
        int sum = 0;
        FibonacciSequence fibonacciSequence = new FibonacciSequence();
//        for (int i = 0; i <= 6; i++) {
//            int temp = fibonacciSequence.fibonacci1(i);
//            stringBuilder.append(temp).append("--->");
//            sum = sum + fibonacciSequence.fibonacci1(i);
//        }

        System.out.println(fibonacciSequence.fibonacci2(6));
        System.out.println("sum-->" + sum);
    }

}